Tree

Time Limit: 10 Sec Memory Limit: 64 MB

Description

给你一棵TREE，以及这棵树上边的距离，问有多少对点它们两者间的距离小于等于K。

Input

第一行一个n，接下来n-1行边描述管道，按照题目中写的输入，接下来是一个k。

Output

仅包括一个整数，表示有多少对点之间的距离小于等于k。

Sample Input

7
　1 6 13
　6 3 9
　3 5 7
　4 1 3
　2 4 20
　4 7 2
　10

Sample Output

5

HINT

n<=40000

Solution

树上路径统计问题，运用点分。
　　每次处理与重心相关的路径，发现如果直接处理两点之间比较困难，我们想到了将所有点加入一个数组，用指针判断加起来<=K的个数，这样的话不一定全是简单路径，但是我们只要减去每个子树中这样操作的条数就一定只剩下简单路径了。
　　点分大概的步骤：
　　1.找出重心；
　　2.计算经过该重心的路径相关需要求的；
　　3.去掉重心对于每棵子树继续做以上过程。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
using namespace std;

const int ONE=80001;

int n,K;
int x,y,z;
int next[ONE],first[ONE],go[ONE],w[ONE],tot;
int center_vis[ONE];
int Max,dist[ONE],num;
int d[ONE];
int center,Ans;

int get()
{
    int res,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

int Add(int u,int v,int z)
{
    next[++tot]=first[u];   first[u]=tot;   go[tot]=v;  w[tot]=z;
    next[++tot]=first[v];   first[v]=tot;   go[tot]=u;  w[tot]=z;
}

namespace PointF
{
    struct power
    {
        int maxx,size;
    }S[ONE];

    void Getsize(int u,int father)
    {
        S[u].size=1;
        S[u].maxx=0;
        for(int e=first[u];e;e=next[e])
        {
            int v=go[e];
            if(v==father || center_vis[v]) continue;
            Getsize(v,u);
            S[u].size+=S[v].size;
            S[u].maxx=max(S[u].maxx,S[v].size);
        }
    }

    void Getcenter(int u,int father,int total)
    {
        S[u].maxx=max(S[u].maxx,total-S[u].size);
        if(Max>S[u].maxx)
        {
            Max=S[u].maxx;
            center=u;
        }

        for(int e=first[u];e;e=next[e])
        {
            int v=go[e];
            if(v==father || center_vis[v]) continue;
            Getcenter(v,u,total);
        }
    }

    void Getdist(int u,int father,int value)
    {
        dist[++num]=value;
        for(int e=first[u];e;e=next[e])
        {
            int v=go[e];
            if(v==father || center_vis[v]) continue;
            Getdist(v,u,value+w[e]);
        }
    }

    int Calc(int u,int value)
    {
        int res=0;
        num=0;

        Getdist(u,0,value);
        sort(dist+1,dist+num+1);

        int l=1,r=num;

        while(l<r)
        {
            while(dist[l]+dist[r]>K && l<r) r--;
            res+=r-l;
            l++;
        }
        return res;
    }

    void Dfs(int u)
    {
        Max=n;
        Getsize(u,0);

        center=u;
        Getcenter(u,0,S[u].size);
        center_vis[center]=true;

        Ans+=Calc(center,0);
        for(int e=first[center];e;e=next[e])
        {
            int v=go[e];
            if(center_vis[v]) continue;
            Ans-=Calc(v,w[e]);
            Dfs(v);
        }
    }
}



int main()
{
    n=get();
    for(int i=1;i<n;i++)
    {
        x=get();    y=get();    z=get();
        Add(x,y,z);
    }

    K=get();
    PointF::Dfs(1);

    printf("%d",Ans);
}